﻿/**
  @(#)$Id: AL_TreeSeq.h 84 2013-10-17 11:36:51Z xiaoting $
  @brief	Tree (tree) that contains n (n> 0) nodes of a finite set, where:
	(1) Each element is called node (node);
	(2) there is a particular node is called the root node or root (root).
	(3) In addition to the remaining data elements other than the root node is divided into m (m ≥ 0) disjoint set of T1, T2, ...... 
	Tm-1, wherein each set of Ti (1 <= i <= m ) itself is a tree, the original tree is called a subtree (subtree).
  
  
  Trees can also be defined as: the tree is a root node and several sub-tree consisting of stars. And a tree is a set defined on the 
  set consisting of a relationship. Elements in the collection known as a tree of nodes, the defined relationship is called 
  parent-child relationship. Parent-child relationship between the nodes of the tree establishes a hierarchy. In this there is a 
  hierarchy node has a special status, this node is called the root of the tree, otherwise known as root.

  We can give form to the tree recursively defined as follows:
	Single node is a tree, the roots is the node itself.
	Let T1, T2, .., Tk is a tree, the root node are respectively n1, n2, .., nk. With a new node n as n1, n2, .., nk's father, then 
	get a new tree node n is the new root of the tree. We call n1, n2, .., nk is a group of siblings, they are sub-node n junction. 
	We also said that n1, n2, .., nk is the sub-tree node n.

	Empty tree is also called the empty tree. Air no node in the tree.

 The related concepts of tree 
  1. Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
  2. Height or depth of the tree: the maximum level of nodes in the tree;
  3. Forests: the m (m> = 0) disjoint trees set of trees called forest;

  The related concepts of tree node 
  1.degree		degree node: A node of the subtree containing the number is called the node degree;
  2.leaf			leaf nodes or terminal nodes: degree 0 are called leaf nodes;
  3.branch		non-terminal node or branch node: node degree is not 0;
  4.parent		parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
  5.child			child node or child node: A node subtree containing the root node is called the node's children;
  6.slibing		sibling nodes: nodes with the same parent node is called mutual sibling;
  7.ancestor		ancestor node: from the root to the node through all the nodes on the branch;
  8.descendant	descendant nodes: a node in the subtree rooted at any node is called the node's descendants.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-17 19:36:51 +0800 (周四, 17 十月 2013) $
  @Revision $Revision: 84 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeSeq.h 84 2013-10-17 11:36:51Z xiaoting $
 */

#ifndef CXX_AL_TREESEQ_H
#define CXX_AL_TREESEQ_H

#ifndef CXX_AL_LISTSEQ_H
#include "AL_ListSeq.h"
#endif

#ifndef CXX_AL_QUEUESEQ_H
#include "AL_QueueSeq.h"
#endif

#ifndef CXX_AL_TREENODESEQ_H
#include "AL_TreeNodeSeq.h"
#endif


///////////////////////////////////////////////////////////////////////////
//			AL_TreeSeq
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_TreeSeq
{
public:
	static const DWORD TREESEQ_DEFAULTSIZE			= 100;
	static const DWORD TREESEQ_MAXSIZE				= 0xffffffff;
	static const DWORD TREESEQ_HEIGHTINVALID		= 0xffffffff;

	/**
	* Construction
	*
	* @param	DWORD dwSize (default value: TREESEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention
	*/
	AL_TreeSeq(DWORD dwSize = TREESEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention 
	*/
	~AL_TreeSeq();

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the tree has data?
	* @attention
	*/
	BOOL IsEmpty() const;
	
	/**
	* GetRootNode
	*
	* @param
	* @return	const AL_TreeNodeSeq<T>*
	* @note Get the root data
	* @attention 
	*/
	const AL_TreeNodeSeq<T>* GetRootNode() const;

	/**
	* GetDegree
	*
	* @param
	* @return	DWORD
	* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
	* @attention 
	*/
	DWORD GetDegree() const;


	/**
	* GetHeight
	*
	* @param	
	* @return	DWORD
	* @note Height or depth of the tree: the maximum level of nodes in the tree;
	* @attention 
	*/
	DWORD GetHeight() const;

	/**
	* GetNodesNum
	*
	* @param
	* @return	DWORD
	* @note get the notes number of the tree 
	* @attention 
	*/
	DWORD GetNodesNum() const;

	/**
	* Clear
	*
	* @param
	* @return	
	* @note 
	* @attention 
	*/
	VOID Clear();

	/**
	* LevelOrderTraversal
	*
	* @param	AL_ListSeq<T>& listOrder <OUT>
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(AL_ListSeq<T>& listOrder) const;

	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listSibling) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listAncestor) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listDescendant) const;

	/**
	* InsertRoot
	*
	* @param	const T& tData <IN> 
	* @return	BOOL
	* @note
	* @attention
	*/
	BOOL InsertRoot(const T& tData);

	/**
	* InsertAtNode
	*
	* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
	* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, DWORD dwIndex, const T& tData);

	/**
	* InsertLeftAtNode
	*
	* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertLeftAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, const T& tData);

	/**
	* InsertRightAtNode
	*
	* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertRightAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, const T& tData);

	/**
	* Remove
	*
	* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
	*/
	BOOL Remove(AL_TreeNodeSeq<T>* pCurTreeNode);

	/**
	* GetChildNodeAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	DWORD dwIndex <IN>
	* @return	const AL_TreeNodeSeq<T>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (dwIndex)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeSeq<T>* GetChildNodeAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, DWORD dwIndex) const;

	/**
	* GetChildNodeLeftAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeSeq<T>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeSeq<T>* GetChildNodeLeftAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode) const;

	/**
	* GetChildNodeRightAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeSeq<T>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeSeq<T>*  GetChildNodeRightAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode) const;

protected:
private:
	/**
	* LevelOrderTraversal
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listOrder) const;

	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant) const;
	
	/**
	* RecalcDegreeHeight
	*
	* @param	
	* @return	BOOL
	* @note recalculate Degree Height
	* @attention 
	*/
	BOOL RecalcDegreeHeight();

	/**
	* GetListDataFormListNode
	*
	* @param	
	* @param	const AL_ListSeq<AL_TreeNodeSeq<T>*>& listNode <IN>
	* @param	AL_ListSeq<T>& listData <OUT>
	* @note
	* @attention 
	*/
	BOOL GetListDataFormListNode(const AL_ListSeq<AL_TreeNodeSeq<T>*>& listNode, AL_ListSeq<T>& listData) const;

	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;
	
	/**
	*Copy Construct
	*
	* @param	const AL_TreeSeq<T>& cAL_TreeSeq
	* @return
	*/
	AL_TreeSeq(const AL_TreeSeq<T>& cAL_TreeSeq);

	/**
	*Assignment
	*
	* @param	const AL_TreeSeq<T>& cAL_TreeSeq
	* @return	AL_TreeSeq<T>&
	*/
	AL_TreeSeq<T>& operator = (const AL_TreeSeq<T>& cAL_TreeSeq);

public:
protected:
private:
	AL_TreeNodeSeq<T>*					m_pTreeNode;			
	DWORD								m_dwMaxSize;
	DWORD								m_dwUsed;

	DWORD								m_dwDegree;
	DWORD								m_dwHeight;
	DWORD								m_dwNumNodes;
	AL_TreeNodeSeq<T>*					m_pRootNode;
};

///////////////////////////////////////////////////////////////////////////
//			AL_TreeSeq
///////////////////////////////////////////////////////////////////////////

/**
* Construction
*
* @param	DWORD dwSize (default value: TREESEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T> 
AL_TreeSeq<T>::AL_TreeSeq(DWORD dwSize):
m_pTreeNode(NULL),
m_dwMaxSize(dwSize),
m_dwUsed(0x00),
m_dwDegree(0x00),
m_dwHeight(TREESEQ_HEIGHTINVALID),
m_dwNumNodes(0x00),
m_pRootNode(NULL)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention 
*/
template<typename T> 
AL_TreeSeq<T>::~AL_TreeSeq()
{
	if (NULL != m_pTreeNode) {
		delete[] m_pTreeNode;
		m_pTreeNode = NULL;
	}
	m_dwMaxSize = 0x00;
	Clear();
}

/**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note the tree has data?
* @attention
*/
template<typename T> BOOL 
AL_TreeSeq<T>::IsEmpty() const
{
	return (0x00 == m_dwNumNodes) ? TRUE:FALSE;
}

/**
* GetRootNode
*
* @param
* @return	const AL_TreeNodeSeq<T>*
* @note Get the root data
* @attention 
*/
template<typename T> const AL_TreeNodeSeq<T>* 
AL_TreeSeq<T>::GetRootNode() const
{
	return m_pRootNode;
}

/**
* GetDegree
*
* @param
* @return	DWORD
* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
* @attention 
*/
template<typename T> DWORD 
AL_TreeSeq<T>::GetDegree() const
{
	return m_dwDegree;
}


/**
* GetHeight
*
* @param	
* @return	DWORD
* @note Height or depth of the tree: the maximum level of nodes in the tree;
* @attention 
*/
template<typename T> DWORD 
AL_TreeSeq<T>::GetHeight() const
{
	return m_dwHeight;
}

/**
* GetNodesNum
*
* @param
* @return	DWORD
* @note get the notes number of the tree 
* @attention 
*/
template<typename T> DWORD 
AL_TreeSeq<T>::GetNodesNum() const
{
	return m_dwNumNodes;
}

/**
* Clear
*
* @param
* @return	
* @note 
* @attention 
*/
template<typename T> VOID 
AL_TreeSeq<T>::Clear()
{
	m_dwUsed = 0x00;
	m_dwDegree = 0x00;
	m_dwHeight = TREESEQ_HEIGHTINVALID;
	m_dwNumNodes = 0x00;
	m_pRootNode = NULL;
}

/**
* LevelOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeSeq<T>::LevelOrderTraversal(AL_ListSeq<T>& listOrder) const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeSeq<T>*> listNode;
	if (TRUE == LevelOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder);
	}

	return FALSE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetSiblingAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listSibling) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeSeq<T>*> listNode;
	if (TRUE == GetSiblingAtNode(pCurTreeNode, listNode)) {
		listSibling.Clear();
		return GetListDataFormListNode(listNode, listSibling);
	}

	return FALSE;
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetAncestorAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listAncestor) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeSeq<T>*> listNode;
	if (TRUE == GetAncestorAtNode(pCurTreeNode, listNode)) {
		listAncestor.Clear();
		return GetListDataFormListNode(listNode, listAncestor);
	}

	return FALSE;
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetDescendantAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<T>& listDescendant) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeSeq<T>*> listNode;
	if (TRUE == GetDescendantAtNode(pCurTreeNode, listNode)) {
		listDescendant.Clear();
		return GetListDataFormListNode(listNode, listDescendant);
	}

	return FALSE;
}

/**
* InsertRoot
*
* @param	const T& tData <IN> 
* @return	BOOL
* @note
* @attention
*/
template<typename T> BOOL 
AL_TreeSeq<T>::InsertRoot(const T& tData)
{
	return InsertAtNode(NULL, 0x00, tData);
}

/**
* InsertAtNode
*
* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::InsertAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, DWORD dwIndex, const T& tData)
{
	if (TRUE == IsEmpty()) {
		if (NULL != pCurTreeNode) {
			//error can not insert to the current node pCurTreeNode, is not exist in the tree
			return FALSE;
		}
		else {
			m_pTreeNode[m_dwUsed].SetData(tData);
			m_pTreeNode[m_dwUsed].SetLevel(0x00);

			m_pRootNode = &m_pTreeNode[m_dwUsed];
			m_dwUsed++;
			m_dwDegree = 0x00;
			m_dwHeight = 0x00;			//empty tree 0xffffffff (-1)
			m_dwNumNodes++;
			return TRUE;
		}
	}

	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if (TRUE == IsFull()) {
		// full, need to get more work buffer 
		//can not support Dynamic Expansion
		return FALSE;
		GetBuffer();
	}

	//inset to the current tree node
	m_pTreeNode[m_dwUsed].SetData(tData);
	m_pTreeNode[m_dwUsed].SetLevel(pCurTreeNode->GetLevel() + 1);
	if (FALSE ==  pCurTreeNode->Insert(dwIndex, &m_pTreeNode[m_dwUsed])) {
		return FALSE;
	}

	DWORD dwCurNodeDegree = 0x00;
	//loop all node to get the current node degree
	if (m_dwDegree < pCurTreeNode->GetDegree()) {
		m_dwDegree = pCurTreeNode->GetDegree();
	}

	if (m_dwHeight < m_pTreeNode[m_dwUsed].GetLevel()) {
		m_dwHeight = m_pTreeNode[m_dwUsed].GetLevel();
	}
	m_dwUsed++;
	m_dwNumNodes++;

	return TRUE;
}

/**
* InsertLeftAtNode
*
* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::InsertLeftAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, const T& tData)
{
	return InsertAtNode(pCurTreeNode, 0x00, tData);
}

/**
* InsertRightAtNode
*
* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::InsertRightAtNode(AL_TreeNodeSeq<T>* pCurTreeNode, const T& tData)
{
	if (NULL == pCurTreeNode) {
		//insert to the root
		return InsertAtNode(NULL, 0x00, tData);
	}

	return InsertAtNode(pCurTreeNode, pCurTreeNode->GetDegree(), tData);
}

/**
* Remove
*
* @param	AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
*/
template<typename T> BOOL
AL_TreeSeq<T>::Remove(AL_TreeNodeSeq<T>* pCurTreeNode)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeSeq<T>*> listTreeNodeDescendant;
	AL_TreeNodeSeq<T>* pTreeNodeDescendant = NULL;
	if (TRUE == pCurTreeNode->GetDescendant(listTreeNodeDescendant)) {
		//delete the descendant node
		for (DWORD dwRemoveCnt=0x00; dwRemoveCnt<listTreeNodeDescendant.Length(); dwRemoveCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwRemoveCnt,pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					pTreeNodeDescendant->Clear();
				}
				else {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
	}

	AL_TreeNodeSeq<T>* pNodeParent = pCurTreeNode->GetParent();
	if (NULL == pNodeParent && m_pRootNode != pCurTreeNode) {
		//not root node and has no parent node
		return FALSE;
	}
	if (NULL != pNodeParent) {
		//parent exist, remove the child node (pCurTreeNode)
		pNodeParent->Remove(pCurTreeNode);
	}
	
	if (m_pRootNode == pCurTreeNode) {
		//remove the root node
		m_pRootNode = NULL;
	}

	pCurTreeNode->Clear();
	m_dwNumNodes -= (listTreeNodeDescendant.Length() + 1);

	if (FALSE == RecalcDegreeHeight()){
		return FALSE;
	}
	
	return TRUE;
}

/**
* GetChildNodeAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	DWORD dwIndex <IN>
* @return	const AL_TreeNodeSeq<T>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (dwIndex)
* @attention the current tree node must be in the tree
*/
template<typename T> const AL_TreeNodeSeq<T>* 
AL_TreeSeq<T>::GetChildNodeAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, DWORD dwIndex) const
{
	if (NULL == pCurTreeNode) {
		return NULL;
	}

	return pCurTreeNode->GetChild(dwIndex);
}

/**
* GetChildNodeLeftAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeSeq<T>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
* @attention the current tree node must be in the tree
*/
template<typename T> const AL_TreeNodeSeq<T>* 
AL_TreeSeq<T>::GetChildNodeLeftAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode) const
{
	return GetChildNodeAtNode(pCurTreeNode, 0x00);
}

/**
* GetChildNodeRightAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeSeq<T>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
* @attention
*/
template<typename T> const AL_TreeNodeSeq<T>* 
AL_TreeSeq<T>::GetChildNodeRightAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode) const
{
	if (NULL == pCurTreeNode) {
		return NULL;
	}

	return GetChildNodeAtNode(pCurTreeNode, pCurTreeNode->GetDegree());
}


/**
* LevelOrderTraversal
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listOrder <OUT>
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeSeq<T>::LevelOrderTraversal(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	listOrder.Clear();
	/*
	AL_ListSeq<AL_TreeNodeSeq<T>*> listNodeOrder;
	listNodeOrder.InsertEnd(const_cast<AL_TreeNodeSeq<T>*>(pCurTreeNode));
	//loop the all node
	DWORD dwNodeOrderLoop = 0x00;
	AL_TreeNodeSeq<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeSeq<T>* pNodeOrderChild = NULL;
	while (TRUE == listNodeOrder.Get(pNodeOrderLoop, dwNodeOrderLoop)) {
		dwNodeOrderLoop++;
		if (NULL != pNodeOrderLoop) {
			listOrder.InsertEnd(pNodeOrderLoop->GetData());
			for (DWORD dwCnt=0x00; dwCnt<pNodeOrderLoop->GetDegree(); dwCnt++) {
				pNodeOrderChild = pNodeOrderLoop->GetChild(dwCnt);
				if (NULL != pNodeOrderChild) {
					//get the descendant
					listNodeOrder.InsertEnd(pNodeOrderChild);
				}
				else {
					//error can not get the descendant
					return FALSE;
				}
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
	*/
	
	AL_QueueSeq<AL_TreeNodeSeq<T>*> queueOrder;
	queueOrder.Push(const_cast<AL_TreeNodeSeq<T>*>(pCurTreeNode));
	
	AL_TreeNodeSeq<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeSeq<T>* pNodeOrderChild = NULL;
	while (FALSE == queueOrder.IsEmpty()) {
		if (TRUE == queueOrder.Pop(pNodeOrderLoop)) {
			if (NULL != pNodeOrderLoop) {
				listOrder.InsertEnd(pNodeOrderLoop); 
				for (DWORD dwCnt=0x00; dwCnt<pNodeOrderLoop->GetDegree(); dwCnt++) {
					pNodeOrderChild = pNodeOrderLoop->GetChild(dwCnt);
					if (NULL != pNodeOrderChild) {
						queueOrder.Push(pNodeOrderChild);
					}
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetSiblingAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listSibling.Clear();
	return pCurTreeNode->GetSibling(listSibling);
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetAncestorAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listAncestor.Clear();
	return pCurTreeNode->GetAncestor(listAncestor);
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeSeq<T>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeSeq<T>::GetDescendantAtNode(const AL_TreeNodeSeq<T>* pCurTreeNode, AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listDescendant.Clear();
	return pCurTreeNode->GetDescendant(listDescendant);
}

/**
* RecalcDegreeHeight
*
* @param	
* @return	BOOL
* @note recalculate Degree Height
* @attention 
*/
template<typename T> BOOL 
AL_TreeSeq<T>::RecalcDegreeHeight()
{
	if (NULL == m_pRootNode) {
		if (TRUE == IsEmpty()) {
			m_dwDegree = 0x00;
			m_dwHeight = TREESEQ_HEIGHTINVALID;
			return TRUE;
		}
		else {
			return FALSE;
		}
	}
	m_dwDegree = m_pRootNode->GetDegree();
	m_dwHeight = m_pRootNode->GetLevel();

	//loop all the node
	AL_ListSeq<AL_TreeNodeSeq<T>*> listTreeNodeDescendant;
	if (TRUE == m_pRootNode->GetDescendant(listTreeNodeDescendant)) {
		DWORD dwNumNodes = listTreeNodeDescendant.Length() + 1;
		if (m_dwNumNodes != dwNumNodes) {
			return FALSE;
		}

		AL_TreeNodeSeq<T>* pTreeNodeDescendant = NULL;
		for (DWORD dwLoopCnt=0x00; dwLoopCnt<listTreeNodeDescendant.Length(); dwLoopCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwLoopCnt, pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					if (m_dwDegree < pTreeNodeDescendant->GetDegree()) {
						m_dwDegree = pTreeNodeDescendant->GetDegree();
					}
					if (m_dwHeight < pTreeNodeDescendant->GetLevel()) {
						m_dwHeight = pTreeNodeDescendant->GetLevel();
					}
				}
				else {
					//error
					return FALSE;
				}
			}
			else {
				//error
				return FALSE;
			}
		}
	}
	return TRUE;
}

/**
* GetListDataFormListNode
*
* @param	
* @param	const AL_ListSeq<AL_TreeNodeSeq<T>*>& listNode <IN>
* @param	AL_ListSeq<T>& listData <OUT>
* @note
* @attention 
*/
template<typename T> BOOL
AL_TreeSeq<T>::GetListDataFormListNode(const AL_ListSeq<AL_TreeNodeSeq<T>*>& listNode, AL_ListSeq<T>& listData) const
{
	AL_TreeNodeSeq<T>* pNodeLoop = NULL;
	listData.Clear();
	//loop all node in list
	for (DWORD dwLoopCnt=0x00; dwLoopCnt<listNode.Length(); dwLoopCnt++) {
		if (TRUE == listNode.Get(dwLoopCnt, pNodeLoop)) {
			if (NULL != pNodeLoop) {
				if (FALSE == listData.InsertEnd(pNodeLoop->GetData())) {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T> VOID 
AL_TreeSeq<T>::GetBuffer()
{
	if ( (FALSE == IsFull()) && (NULL != m_pTreeNode) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pTreeNode) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pTreeNode = new AL_TreeNodeSeq<T>[m_dwMaxSize];
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	AL_TreeNodeSeq<T>* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pTreeNode;
	if (TREESEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (TREESEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = TREESEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pTreeNode = new AL_TreeNodeSeq<T>[m_dwMaxSize];
	}
	//need to copy the last to the current
	for (DWORD dwCpy=0x00; dwCpy<GetNodesNum(); dwCpy++) {
		m_pTreeNode[dwCpy] = pLastTpye[dwCpy];
	}

	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param VOID
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL 
AL_TreeSeq<T>::IsFull() const
{
	return (m_dwMaxSize <= GetNodesNum()) ? TRUE:FALSE;
}
#endif // CXX_AL_TREESEQ_H
/* EOF */